/**
 * AspectSense project
 *
 * Middleware for annotation-based, context-aware and adaptive services for
 * mobile and ubiquitous computing
 *
 * This project is an open-source effort, started at the University of Cyprus
 * [http://www.ucy.ac.cy].
 *
 * More information about the project is available at
 * [http://code.google.com/p/aspectsense]
 *
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the Free
 * Software Foundation; either version 2.1 of the License, or (at your option)
 * any later version.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

package org.aspectsense.example_apps.sorted_helloworld;

import org.aspectsense.annotations.Component;
import org.aspectsense.annotations.Service;
import org.aspectsense.annotations.ServiceUtility;
import org.aspectsense.framework.DefaultComponent;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * <p/>
 * Date: Sep 18, 2007<br/>
 * Time: 5:42:31 PM
 * </p>
 *
 * @author Nearchos Paspallis [nearchos@cs.ucy.ac.cy]
 */
@Component(
        displayID = "MergeSortImpl",
        description = "Implements the merge-sort algorithm"
)
@Service(
        serviceType = SortingService.class
)
@ServiceUtility(
        targetServiceType = SortingService.class,
        utilityFunction = "context[context.infrastructure.cpu-availability]"
)
public class MergeSortImpl extends DefaultComponent implements SortingService
{
    public List<String> sort(final Set<String> input)
    {
        final List<String> workingList = new LinkedList<String>(input);

        return mergesort(workingList);
    }

    private List<String> mergesort(final List<String> input)
    {
        final int length = input.size();
        if(length <= 1)
        {
            return input;
        }

        int middle = input.size() / 2;

        List<String> left = new LinkedList<String>();
        List<String> right = new LinkedList<String>();
        for(int i = 0; i < middle; i++)
        {
            left.add(input.get(i));
        }
        for(int j = middle; j < length; j++)
        {
            right.add(input.get(j));
        }

        left = mergesort(left);
        right = mergesort(right);

        return merge(left, right);
    }

    private List<String>  merge(final List<String> left, final List<String> right)
    {
        List<String> result = new LinkedList<String>();

        while(left.size() > 0 && right.size() > 0)
        {
            if(left.get(0).compareTo(right.get(0)) <= 0)
            {
                result.add(left.remove(0));
            }
            else
            {
                result.add(right.remove(0));
            }
        }

        if(left.size() == 0)
        {
            while(right.size() > 0)
            {
                result.add(right.remove(0));
            }
        }

        if(right.size() == 0)
        {
            while(left.size() > 0)
            {
                result.add(left.remove(0));
            }
        }

        return result;
    }
}